/**
 * problem_016.c
 * Copyright (C) 2011-03-18 - xrose
 * What is the sum of the digits of the number 2^1000
 */

#include <stdio.h>
#include <math.h>
#include <stdlib.h>

//char* binpow(int n, char* bpow);
char* binpow(int n);
int main (int argc, char *argv[])
{
    char *buff;
    int i=0;
    int sumi=0;
    buff = binpow(1000);
    printf("___%s\n", buff);
    while(buff[i]!='\0')
    {
        sumi+=(buff[i]-48);
        i++;
    }
    printf("__sum = %d\n", sumi);
    free(buff);
    return 0;
}

//char* binpow(int n, char* bpow)
//{
//    /*calculate 2^n*/
//    int _lgn = floor(n*log10(2.0))+1;
//    int i, j;
//    int r = 0;
//    int tmp=0;
//    //must use a pointer to control bpow
//    char *ptr = bpow;
//
//    for(i=0; i<_lgn-1; i++)
//    {
//        ptr[i] = 0;
//    }
//    ptr[_lgn-1] = 1;
//
//    if(n == 0)
//    {
//        return bpow;
//    }
//    for(i = 1; i <= n; i++)
//    {
//        for(j=_lgn-1; j>=0; j--)
//        {
//            tmp = ptr[j] + ptr[j] +r;
//            if(tmp < 10)
//            {
//                ptr[j] = tmp;
//                r = 0;
//            } else
//            {
//                ptr[j] = tmp - 10;
//                r = 1;
//            }
//        }
//    }
//    return bpow;
//}

char* binpow(int n)
{
    /*calculate 2^n*/
    int _lgn = floor(n*log10(2.0))+1;
    int i, j;
    int r = 0;
    int tmp=0;
    //must use a pointer to control bpow
    char *ptr;

    ptr = (char*) malloc (_lgn+1);
    if (ptr==NULL) exit (1);

    for(i=0; i<_lgn-1; i++)
    {
        ptr[i] = '0';
    }
    ptr[_lgn-1] = '1';
    ptr[_lgn] = '\0';

    if(n == 0)
    {
        return ptr;
    }
    for(i = 1; i <= n; i++)
    {
        for(j=_lgn-1; j>=0; j--)
        {
            tmp = (ptr[j]-48) + (ptr[j]-48) +r;
            if(tmp < 10)
            {
                ptr[j] = tmp+48;
                r = 0;
            } else
            {
                ptr[j] = tmp - 10 + 48;
                r = 1;
            }
        }
    }
    return ptr;
}
